package com.liang.leetcode.binarytree.exercise;

import com.liang.leetcode.binarytree.entity.TreeNode;
import com.liang.leetcode.binarytree.util.BiTreeUtil;

import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * 112.路径总和
 * 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum。
 * 判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和 targetSum。
 * 如果存在返回 true，否则返回 false
 */
public class BiTree15_HasPathSum {
    public static void main(String[] args) {
        // 创建一棵二叉树
        List<Integer> nodeList = Arrays.asList(1, 2, 3, 4, 1);
        TreeNode root = BiTreeUtil.createBiTreeByRecursion(nodeList);
        System.out.println("先序遍历：" + BiTreeUtil.preorderTraversal(root));
        // 二叉树路径总和
        System.out.println(hasPathSum(root, 4));
    }

    /**
     * 解法1：递归，通过递归地减少问题规模（即每次递归时减去一个节点的值）
     */
    private static boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        if (root.left == null && root.right == null && root.val == targetSum) {
            return true;
        }
        return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
    }

    /**
     * 解法2：迭代，用两个栈或者队列，一个用来保存节点，另一个用来保存从根到当前节点路径上所有节点的和
     */
    private static boolean hasPathSum2(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        Stack<TreeNode> stack = new Stack<>();
        Stack<Integer> sumStack = new Stack<>();
        stack.push(root);
        sumStack.push(root.val);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            Integer nodeSum = sumStack.pop();
            // 检查当前节点是否是叶子节点，再比较路径值和target是否相等
            if (node.left == null && node.right == null) {
                if (nodeSum == targetSum) {
                    return true;
                }
                continue;
            }
            // 处理左子节点
            if (node.left != null) {
                stack.push(node.left);
                sumStack.push(nodeSum + node.left.val);
            }
            // 处理右子节点
            if (node.right != null) {
                stack.push(node.right);
                sumStack.push(nodeSum + node.right.val);
            }
        }
        return false;
    }

    /**
     * 解法 3：回溯，正向思维，求路径之和
     */
    private static boolean hasPathSum3(TreeNode root, int targetSum) {
        traversal(root, targetSum);
        return isFlag;
    }

    private static boolean isFlag = false;
    private static int pathSum = 0;

    private static void traversal(TreeNode root, int target) {
        if (root == null) {
            return;
        }
        pathSum += root.val;
        if (root.left == null && root.right == null) {
            if (pathSum == target) {
                isFlag = true;
            }
        } else {
            traversal(root.left, target);
            traversal(root.right, target);
        }
        // 回溯
        pathSum -= root.val;
    }

    /**
     * 解法4：回溯，精简版，将状态作为递归函数的参数传递
     */
    private static boolean hasPathSum4(TreeNode root, int targetSum) {
        return traversal2(root, targetSum, 0);
    }

    private static boolean traversal2(TreeNode root, int target, int currentSum) {
        if (root == null) {
            return false;
        }
        currentSum += root.val;
        // 如果是叶子节点，检查路径和是否等于目标和
        if (root.left == null && root.right == null && currentSum == target) {
            return true;
        }
        // 如果不是叶子节点，递归检查左右子树
        return traversal2(root.left, target, currentSum) || traversal2(root.right, target, currentSum);
    }

}
